package xing.rbtree;

/**
 * 本代码中，修改 color 颜色 的 代码 不~~同意~~ 统一 ， color = xx , 以及 setColor ( ) , 均有使用 ，。
 * 
 * @author xing
 * @date 2023/3/7 18:22:26
 */
public class RBTree_2<K extends Comparable<K>, V> {
    private final RBNode<K, V> nilNode = new RBNode<>();
    //    private RBNode<K, V> root = nilNode;
    private RBNode<K, V> root;

    // ----------------------------------
    // ---        delete Node         ---
    // ----------------------------------

    public void delete(K k, V v) {
        delete(k);
    }

    public void delete(K k) {
        if (this.root == null) {
            System.out.println("红黑树为空，删除取消。");
            return;
        }
        // 跟据 key 寻找 node 。 .
        RBNode<K, V> deleteNode = findNode(k);
        if (deleteNode == null) {
            System.out.println("未找到 Node, 删除取消");
            return;
        }
        // 该判定为寻找最终要删除的 Node .
        // 左右子树均不为空， (zhi you 一个子结点时，不需要计算前驱结点，直接上移占他位置, 此时 deleteNode 不变 ) . 。
        if (deleteNode.left != null && deleteNode.right != null) {
            RBNode<K, V> temp = getPrecursor(deleteNode);
            deleteNode.key = temp.key;
            deleteNode.value = temp.value;
            deleteNode = temp;
            temp = null;
        }
        // deleteNode 依然为 root 节点，代表没有后继节点，所以左节点为 null ， 那么令右子节点为 root node .
        if (isRoot(deleteNode)) {
            setRoot(deleteNode.right);
            return;
        }
        // 孩子结点， (用来作为 deleteFixup() 方法的参数，。标记删除节点的位置，。所以当没有子节点，使用 nil 结点替代，。)
        RBNode<K, V> childNode;
        if (deleteNode.left != null) {
            childNode = deleteNode.left;
        } else if (deleteNode.right != null) {
            childNode = deleteNode.right;
        } else {
            childNode = nilNode;
        }
        deleteNode.parent.replaceChildNode(deleteNode, childNode);
        if (isBlack(deleteNode)) {
            deleteFixup(childNode);
        } else {
            deleteIfNilNode(childNode);
        }
    }

    public void deleteFixup(RBNode<K, V> node) {
        while (!isRoot(node)) {
            if (isRed(node)) {
                node.color = RBColor.BLACK;
//                break;
                return;
            }
            RBNode<K, V> parent = node.parent;

            if (parent.left == node) {
                RBNode<K, V> right = parent.right;
                // xiong 第 为 黑
                if (isBlack(right)) {
                    // 兄弟子节点均为黑，兄弟，置红
                    if (isBlack(right.left) && isBlack(right.right)) {
                        // 注意这里如果 right 为 nil 节点，显然有问题，但正常不应该出现这种情况。（因为 nil 不作为正常节点计算黑高，。兄弟节点应该不可能为黑节点，删除不会进入此方法（）。） 所以这里部分判断代码其实没必要写。
                        // if (right == nilNode) {
                        //     throw new RuntimeException("进入了正常永远不会进入的分支");
                        // }
                        right.setColor(RBColor.RED);
                        node = parent;
//                        continue;
                    } else if (isRed(right.right)) {
                        parent.right.color = parent.color;
                        leftRotate(parent);
                        parent.color = RBColor.BLACK;
                        right.right.color = RBColor.BLACK;
//                        return;
                    } else {
                        rightRotate(right);
                        right.setColor(RBColor.BLACK);
                        right.right.setColor(RBColor.RED);
                    }
                } else {
                    right.color = RBColor.BLACK;
                    node = parent;
//                    continue;
                }
                deleteIfNilNode(node.left);

            } else {
                RBNode<K, V> left = parent.left;
                // xiong 第 为 黑
                if (isBlack(left)) {
                    // 兄弟子节点均为黑，兄弟，置红
                    if (isBlack(left.right) && isBlack(left.left)) {
                        left.setColor(RBColor.RED);
                        node = parent;
//                        continue;
                    } else if (isRed(left.left)) {
                        parent.left.color = parent.color;
                        rightRotate(parent);
                        parent.color = RBColor.BLACK;
                        left.left.color = RBColor.BLACK;
//                        return;
                    } else {
                        leftRotate(left);
                        left.setColor(RBColor.BLACK);
                        left.left.setColor(RBColor.RED);
                    }
                } else {
                    left.color = RBColor.BLACK;
                    node = parent;
//                    continue;
                }
                deleteIfNilNode(node.right);

            }

        }
        this.root.color = RBColor.BLACK;
    }

    public void deleteIfNilNode(RBNode<K, V> node) {
        RBNode<K, V> parent;
        if ((parent = nilNode.parent) != null && node == nilNode) {
            parent.replaceChildNode(nilNode, null);
            nilNode.parent = null;
        }
    }

//    public void delete_2(K k) {
//        RBNode<K, V> precursor = getPrecursor(deleteNode);
//    }

    public boolean hasPrecursor(RBNode<K, V> node) {
        return node.left != null;
    }


    public RBNode<K, V> getPrecursor(RBNode<K, V> node) {
        RBNode<K, V> precursor;
        if ((precursor = node.left) == null) {
            return node;
        }
        while (precursor.right != null) {
            precursor = precursor.right;
        }
        return precursor;
    }

//    public void delete(K k, V v) {
//
//    }


    public RBNode<K, V> findNode(K k) {
        RBNode<K, V> tRoot = this.root;
        while (tRoot != null) {
            int cmp = tRoot.key.compareTo(k);
            if (cmp < 0) {
                tRoot = tRoot.right;
            } else if (cmp > 0) {
                tRoot = tRoot.left;
            } else {
                return tRoot;
            }
        }
//        rett
        return null;
    }

    // -------------------------------
    // ---          insert node    ---
    //  -------------------------------

    public void insert(K k) {
        insert(k, null);
    }

    public void insert(K k, V v) {
        if (this.root == null) {
            setRoot(k, v);
            return;
        }
        RBNode<K, V> newNode = new RBNode<>(k, v);
        RBNode<K, V> parent = findParent(k);
        parent.setLeftOrRightAndAsParent(newNode);
        insertFixup(newNode);
    }

    public void insertFixup(RBNode<K, V> node) {
        while (!isRoot(node)) {
            RBNode<K, V> parent;
            // 如果父节点是根节点，（没有祖父节点），根节点为黑色，直接 return , 所以下边一定有 grandParent
            if (isBlack(parent = node.parent)) {
                return;
            }
            RBNode<K, V> grandParent = parent.parent;
            if (grandParent.left == parent) {
                if (isRed(grandParent.right)) {
                    setColorByFourInsert(node);
                    node = grandParent;
                }
                // 为 BLACK 或者为 Null
                else {
                    if (parent.left == node) {
                        rightRotate(grandParent);
                        parent.setColor(RBColor.BLACK);
                        grandParent.setColor(RBColor.RED);
                        node.color = RBColor.RED;
                        return;
                    } else {
                        leftRotate(parent);
                    }
                }
            } else {
                if (isRed(grandParent.left)) {
                    setColorByFourInsert(node);
                    node = grandParent;
                } else {
                    if (parent.right == node) {
                        leftRotate(grandParent);
                        parent.setColor(RBColor.BLACK);
                        grandParent.setColor(RBColor.RED);
                        node.color = RBColor.RED;
                        return;
                    } else {
                        rightRotate(parent);
                    }
                }
            }
        }
        this.root.color = RBColor.BLACK;
    }

    // -----------

    public RBNode<K, V> getRoot() {
        return this.root;
    }

    public void setColorByFourInsert(RBNode<K, V> node) {
//        node.color = RBColor.RED;
        RBNode<K, V> grandParent = node.parent.parent;
        grandParent.right.color = grandParent.left.color = RBColor.BLACK;
        grandParent.color = node.color = RBColor.RED;
    }

    public void leftRotate(RBNode<K, V> node) {
        if (node.right == null) {
            return;
        }
        RBNode<K, V> right = node.right;

        RBNode<K, V> parent = node.parent;
        if (parent == null) {
            setRoot(right);
        } else {
            parent.replaceChildNode(node, right);
        }
//        node.setRright = right.left;
        node.setRightAndAsParent(right.left);
//        right.seleft = node;
        right.setLeftAndAsParent(node);

    }

    private boolean isRoot(RBNode<K, V> node) {
        return node == this.root;
    }

    public void rightRotate(RBNode<K, V> node) {
        if (node.right == null) {
            return;
        }
        RBNode<K, V> left = node.left;
        RBNode<K, V> parent = node.parent;
//        node.left = left.right;
//        left.right = node;
        if (parent == null) {
//            setRoot(lleft);
            setRoot(left);
        } else {
            parent.replaceChildNode(node, left);
        }
//        node.setLeftAndAsParent(left.left);
        node.setLeftAndAsParent(left.right);
        left.setRightAndAsParent(node);
//        node.parent = left;
    }

    public boolean isRed(RBNode<K, V> node) {
        return node != null && node.color == RBColor.RED;
    }

    public boolean isBlack(RBNode<K, V> node) {
        return node == null || node.color == RBColor.BLACK;
    }

    public void setRoot(K k, V v) {
        setRoot(new RBNode<>(k, v));
    }

    public void setRoot(RBNode<K, V> node) {
        this.root = node;
        if (node != null) {
            this.root.setColor(RBColor.BLACK);
            this.root.parent = null;
        }
    }

    public RBNode<K, V> findParent(K k) {
        //
        RBNode<K, V> parent = null;

        RBNode<K, V> tRoot = this.root;
        while (tRoot != null) {
            parent = tRoot;
            if (tRoot.key.compareTo(k) < 0) {
                tRoot = tRoot.right;
            } else {
                tRoot = tRoot.left;
            }
        }
        return parent;
    }

    static class RBNode<K extends Comparable<K>, V> {
        private RBNode<K, V> left;
        private RBNode<K, V> right;
        private RBNode<K, V> parent;
        private RBColor color;
        private K key;
        private V value;

        private RBNode() {
            this.color = RBColor.BLACK;
        }

        public RBNode(K key, V value) {
            this.key = key;
            this.value = value;

            this.color = RBColor.RED;
        }

        public RBNode<K, V> getLeft() {
            return left;
        }

        public void setLeft(RBNode<K, V> left) {
            this.left = left;
        }

        public void setLeftAndAsParent(RBNode<K, V> left) {
            this.left = left;
            if (left != null) {
                left.parent = this;
            }
        }

        public RBNode<K, V> getRight() {
            return right;
        }

        public void setRight(RBNode<K, V> right) {
            this.right = right;
        }

        public void setRightAndAsParent(RBNode<K, V> right) {
            this.right = right;
            if (right != null) {
                right.parent = this;
            }
        }

        public void setLeftOrRight(RBNode<K, V> node) {
            //
            if (this.key.compareTo(node.key) < 0) {
                this.setRightAndAsParent(node);
            } else {
                this.setLeftAndAsParent(node);
            }
        }

        public void replaceChildNode(RBNode<K, V> node, RBNode<K, V> newNode) {
            if (node == this.left) {
                this.setLeftAndAsParent(newNode);
                node.parent = null;
            } else if (node == this.right) {
                this.setRightAndAsParent(newNode);
                node.parent = null;
            } else {
                throw new IllegalArgumentException("replaceChildNode 传入的 Node 不是子节点");
            }
        }

        public void setLeftOrRightAndAsParent(RBNode<K, V> node) {
            if (this.key == null) {
                throw new UnsupportedOperationException("NIl NODE can't set child node");
            }
            this.setLeftOrRight(node);
            if (node != null) {
                node.parent = this;
            }
        }

        public RBNode<K, V> getParent() {
            return parent;
        }

        public void setParent(RBNode<K, V> parent) {
            this.parent = parent;
        }

        public RBColor getColor() {
            return color;
        }

        public void setColor(RBColor color) {
            this.color = color;
        }

        public K getKey() {
            return key;
        }

        public void setKey(K key) {
            this.key = key;
        }

        public V getValue() {
            return value;
        }

        public void setValue(V value) {
            this.value = value;
        }
    }

    static enum RBColor {
        RED,
        BLACK
    }
}
